package solutions.leetcode.easy;

import solutions.lib.BaseSolution;

import java.util.Stack;

/**
 * @author lizhidong
 * <a href="https://leetcode.cn/problems/final-prices-with-a-special-discount-in-a-shop/">1475. 商品折扣后的最终价格</a>
 */
public class Solution1475 extends BaseSolution {

    public int[] finalPrices(int[] prices) {
        Stack<Integer> stack = new Stack<>();
        for (int i = prices.length - 1; i >= 0; i--) {
            int dis = 0;
            while (!stack.isEmpty()) {
                int top = stack.peek();
                if (prices[i] >= top) {
                    dis = top;
                    break;
                } else {
                    stack.pop();
                }
            }
            stack.push(prices[i]);
            prices[i] -= dis;
        }
        return prices;
    }

    public static void main(String[] args) {
        Solution1475 solution = new Solution1475();
        printVals(solution.finalPrices(new int[]{
                10, 1, 1, 6
        }));
    }
}